The function that calculates the permission of transfer is indispensable to conventional network devices in order to ensure conventional security of conventional computer network system, as follows.
Referring to FIG. 33, a conventional computer network will be described. A user or subscriber of the network possesses a user's terminal, such as a computer terminal, for concatenation to the network. A user's terminal is assigned with a specific network address in accordance with a predetermined rule when it is concatenated to the network in order to be distinguished from other user's terminals. Herein, the network address is represented by a numeral of a plurality of digits of, for example, first through third digits (a, b, c). The predetermined rule defines a hierarchical structure of the network address. The predetermined rule defines a hierarchical structure of the network address. For example, the first digit of the numeral represents a nation, such as England, Germany, and Japan. The second digit of the numeral represents a city in the nation, and the third digit of the numeral represents a company name in the city. In the following description, these hierarchical items will be called segments. Referring to FIG. 33, each segment is depicted by a rectangular block. Specifically, the network includes a first segment (SEGMENT 1), second segment (SEGMENT 2), and a third segment (SEGMENT 3) at a highest hierarchical level. The first segment (SEGMENT 1) includes the fourth segment (SEGMENT 4) and the fifth segment (SEGMENT 5). Likewise, the second segment (SEGMENT 2) and the third segment (SEGMENT 3) include the sixth segment (SEGMENT 6) and the seventh segment (SEGMENT 7), respectively. A user's terminal (PC) 401-1 exists in the fourth segment. Likewise, a user's terminal (PC) 401-2 and a user's terminal (PC) 401-3 exists in the sixth segment. The first segment possesses a network address (1, *, *) in which a first digit alone is specified as “1”. The fourth segment subordinate to the first segment possesses a network address (1, 2, *) in which first and second digits “1” and “2” are specified. Like wise, the fifth segment subordinate to the first segment possesses a network address (1, 3 *) in which first and second digits “1” and “3” are specified. Thus, the user's terminal 401-1 in the fourth segment possesses a specific or unique network address (1, 2, 6). The second segment possesses a network address (2, *, *) in which a first digit alone is specified as “2”. The sixth segment subordinate to the second segment possesses a network address (2, 3, *) in which first and second digits “2” and “3” are specified. Thus, the user's terminal 401-2 and 402-3 in the sixth segment possesses a specific or unique network address (2, 3, 4) and (2, 3, 5) respectively. The third segment possesses a network address (3, *, *) in which a first digit alone is specified as “3”. The seventh segment subordinate to the third segment possesses network address (3, 5, *) in which first and second digits “3” and “5” are specified. A symbol “*” contained in these addresses represents “don't care”.
Each digit of each network address is represented by a binary number of three bits. Thus, each network address is represented by a bit sequence of nine bits in total. For example, a network address (1, 2, *) is represented by a bit sequence (001, 010, 000). In the following description, these bit sequences will be called storage data. Since the symbol “*” represents “don't care” for the third digit, it is necessary to indicate that the first six bits (001, 010) in the storage data (001, 010, 000) alone are valid and the remaining bits (000) are invalid. For this purpose, mask information (or mask data) is combined with storage data. In the following description, these pairs will be called structured data. In the illustrated example, the mask information (or mask data) is given by a bit sequence (111, 111, 000). Herein, “0” and “1” represent a mask invalid state and a mask valid state, respectively.
In order to concatenate or establish communication between a plurality of user's terminals in the network, each segment is provided with a network device, for example, a router. As illustrated in FIG. 33, the first segment, the second segment, the third segment, the forth segment, the fifth segment, the sixth segment, and the seventh segment are provided with the first network device 400-1, the second network device 400-2, the third network device 400-3, the fourth network device 400-4, the fifth network device 400-5, the sixth network device 400-6, and the seventh network device 400-7, respectively. As illustrated in FIG. 33, each network device is concatenated to any user's terminals or any network devices subordinate to the corresponding segment. In addition, the first network device 400-1 is concatenated to the network device 400-2, the network device 400-3, and the network device 400-6.
Each network device in the corresponding segment is supplied from any user's terminals or any network devices concatenated to the network devices with communication data, and a source network address and destination network address annexed thereto. With reference to the source network address, the destination network address and predetermined transfer rule, the network device calculates a permission of transfer. Furthermore, with reference to the destination network address and the relationship of connection of network apparatuses, the network device calculates an optimum transfer route and produces a transfer network address. Herein, the network device controls a communication data transfer.
Herein, description will be made about the case where the associative memory is applied to the network device 400-1 in FIG. 33. It is assumed that the transferring the input data to a network device 400-6 having a network address (2, 3, *) is more optimum than to another network device 400-2 having a network address (2, *, *). In other words, it is optimum here to select the network device having the least number of bits in a mask valid state, in the network devices corresponding to the network address coincident with each other, taking the destination network address and the mask information into account, into a valid state.
Table 1(a) shows one setting of transfer rule in the computer network described in this example.
TABLE 1(a)TRANSFERPERMIT TRANSFER FROM THE INTERNAL OFRULE 1:SEGMENT 4 TO THE INTERNAL OF SEGMENT 2TRANSFERPERMIT TRANSFER FROM THE INTERNAL OFRULE 2:SEGMENT 1 TO THE INTERNAL OF SEGMENT 3TRANSFERREJECT TRANSFER FROM THE INTERNAL OFRULE 3:SEGMENT 4 TO THE INTERNAL OF SEGMENT 6TRANSFERPERMIT TRANSFER FROM INTERNAL P0401-1 OFRULE 4:SEGMENT 4 TO INTERNAL PC401-2 OF SEGMENT 6TRANSFERREJECT TRANSFER FROM THE INTERNAL OFRULE 5:SEGMENT 1 TO INTERNAL PC401-3 OF SEGMENT 6
TABLE 1(b)TRANSFERSOURCEDESTINATIONPERMIT = 1RULENETWORK ADDRESSNETWORK ADDRESSREJECT = 01(1. 2. *)(2. *. *)1STORAGE DATASTORAGE DATA“001 010 000” = (1. 2. 0)“010 000 000” = (2. 0. 0)MASK INFORMATIONMASK INFORMATION“111 111 000” = (7. 7. 0)“111 000 000” = (7. 7. 0)2(1. *. *)(3. *. *)1STORAGE DATASTORAGE DATA“001 000 000” = (1. 0. 0)“011 000 000” = (3. 0. 0)MASK INFORMATIONMASK INFORMATION“111 000 000” = (7. 7. 0)“111 000 000” = (7. 0. 0)3(1. 2. *)(2. 3. *)0STORAGE DATASTORAGE DATA“001 010 000” = (1. 2. 0)“010 011 000” = (2. 3. 0)MASK INFORMATIONMASK INFORMATION“111 111 000” = (7. 7. 0)“111 111 000” = (7. 7. 0)4(1. 2. 6)(2. 3. 4)1STORAGE DATASTORAGE DATA“001 010 110” = (1. 2. 6)“010 011 100” = (2. 3. 4)MASK INFORMATIONMASK INFORMATION“111 111 111” = (7. 7. 7)“111 111 111” = (7. 7. 7)5(1. *. *)(2. 3. 5)0STORAGE DATASTORAGE DATA“001 000 000” = (1. 0. 0)“010 011 101” = (2. 3. 5)MASK INFORMATIONMASK INFORMATION“111 000 000” = (7. 0. 0)“111 111 111” = (7. 7. 7)Rule 1 defines that transfer from subordinate to segment 4 to subordinate to segment 2 is permitted. Rule 2 defines that transfer from subordinate to segment 1 to subordinate to segment 3 is permitted. Rule 3 defines that transfer from subordinate to segment 4 to subordinate to segment 6 is prohibited. Rule 4 defines that transfer from PC401-1 subordinate to segment 4 to PC401-2 subordinate to segment 6 is permitted. Rule 5 defines that transfer from subordinate to segment 1 to PC401-3 subordinate to segment 6 is prohibited. When source network address and destination network address are represented by a pair of storage data and mask information, the transfer rule of Table1(a) can be described as Table1(b). These transfer rules are necessary for security of computer network system. In case of the transfer from segment 4 to segment 6 under the transfer rule of Table1(a), vital data stored in PC401-3, for example, can be protected from unlawful access, copy, falsification, and elimination, because only the transfer from PC401-1 to PC401-2 is permitted and all other transfer is prohibited.
Herewith, the user's terminals are not directly connected by the use of the communication channels but carry out communication by controlling the transfer of communication data by the use of communication control functions of the network devises. Thus, communication channels as limited resources are saved while security is ensured.
Next, referring to FIG. 34, the conventional network device 422 is used in the network devise 400-1 in FIG. 33.
The network device 422 is supplied with input transfer data 402, and produce output transfer data 403. The input transfer data 402 comprises a source network address 404, a transfer network address 405, a destination network address 406, and data division 407. The output transfer data 403 comprises a source network address 406, a second transfer network address 408, a destination network address 406, and data division 407. Since the conventional network device 422 is used in the network device 400-1 of FIG. 33, as will readily be understood, the transfer network address 405 in the input transfer data 402 is the network address of the network devise 400-1 itself in FIG. 34.
The network device 422 comprises a source network address 409, a destination network address 410, an associative memory 101, a CPU 413, an encoder 414, a memory 416, a transfer network address changing section 418, and data transfer division 421.
The source network address extracting section 409 extracts the source network address 404 contained in the input transfer data 402, and supplies it to the CPU 413 as the source network address 411. The destination network address extracting section 410 extracts the destination network address 402 contained in the input transfer data 402, and supplies it to the associative memory 101 and the CPU 413 as the destination network address 412.
Among the network devices concatenated with the network device 422 in the network, the network address of the segment of the network device out of the network to which the network device 422 belongs, is memorized in the associative memory word 102 in the associative memory 101 of the network device 422. Herein, in FIG. 34, description will be made about the case where the conventional network device is used in the network device 400-1 in FIG. 33. The network address (2, *, *), to which the network device 400-2 belongs, is memorized in the associative memory word 102-1. Specifically, the associative memory word 102-1 stores in binary numbers the storage data (010, 000, 000) and the mask information (111,000,000) to implement (2, *, *) represented by structured data format. Likewise, the network address (2, 3, *), to which the network device 400-6 belongs, is memorized in the associative memory word 102-2, and the network address (3, *, *), to which the network device 400-3 belongs, is memorized in the associative memory word 103-3, respectively. The associative memory 101 possesses searching (or retrieving) function or mask searching function in addition to write/read functions of writing and reading storage data (namely, the address data) at a designated memory address in the matter similar to an ordinary memory circuit. Specifically, the associative memory 101 possesses the mask searching function to put the only match line 115 corresponding to the storage data with the least number of bits in a mask valid state, in the match lines 105-1 through 105-3 corresponding to one of the storage data coincident with the input destination network address 412 taking the mask information into account, into a valid state. The pending patent application 2000-181406 can be cited as one example of the associative memory 101.
The encoder 414 encodes the match lines 105-1 through 105-3, supplied by the associative memory 101, into a memory address signal 415. The memory 416 stores the network addresses of the network device corresponding to the segment network addresses, each of which comprises the storage data and the mask information, and each of which is stored in each associative memory word of the associative memory 101. In the memory 416, each network device network address is memorized in a word corresponding to the associative memory word of the associative memory 101 where a corresponding network address is memorized. For example, the network address (2, *, *) is stored in the first associative memory word 102-1 of the associative memory 101 while the network address of the network device 400-2 (FIG. 33) corresponding thereto is stored in the first word of the memory 416. Similarly, the network address of the network device 400-6, the network address of the network device 400-3, are stored in the second word and the third word of the memory 416, respectively. Supplied with the memory address signal 415 as a read address, the memory 416 produces a memory data signal 417 stored in the word designated by the memory address signal 415.
The transfer network address 418 produces the changed transfer data 419 by changing the transfer network address 405 of input transfer data 402 into memory data signal 417, and supplies it to the data transfer division 421. The CPU 413 determines the transfer permission under the rule indicated in the table (a), and supplies the result of the determination to the data transfer field 421 as the transfer control signal 420. The data transfer division 421 produces the changed transfer data 419 as the output transfer data 403 when the transfer control signal 420 permits the transfer. Otherwise, the data transfer division 421 does not produce the changed transfer data when the transfer control signal prohibits the transfer.
It is assumed that the source network address 404 in the input transfer data 402 is (1, 2, 3), and the destination network address 405 in the input transfer data 402 is (3, 5, 6). Upon completion of the searching operation in the associative memory 101, the match line 105-3 corresponding to the network address (3, *, *) in the associative memory word 102-3 alone is put into a valid state. Then, the encoder 414 produces “3” as the memory address 403. The memory 416 produces the memory data signal 417 representative of the network address of the network device 400-3. The transfer network address changing section 418 changes the transfer network address 405 in the input transfer data 402 into the network address of the network device 400-3, and supplies it to the data transfer field 421 as the changed transfer data 419. Since the source network address information 411 is (1, 2, 3) and the destination network address information 412 is (3, 5, 6), CPU 413 applies the transfer rule 2, and supplies the transfer control signal 420 to the data transfer field 421 with transfer permitted state. Consequently, the data transfer field 421 transfers the changed transfer data 419 as the output transfer data 403 to the router 400-3. The router 400-3 is responsive to the transfer data and performs the operation similar to that mentioned above. Thus, the transfer data are successively transferred with security from network devices to network devices on the optimised route until the user's terminal at the destination network address (3, 5, 6) is reached.
[Description of the Conventional Associative Memory]
Herein, referring to FIG. 28, a typical conventional associative memory will be described. An associative memory 101 comprises a two-input/one-output n-bit selector 123, first through m-th n-bit associative memory words 102, an n-bit latch 121, a controller 130, and the first through n-th logical gate 116. The j-th associative memory word 102-j combines the associative memory cells 107-j-1 through 107-j-n, n in number. The j-th associative memory word 102-j (where j is and integer variable between 1 and m, both inclusive) comprises first through n-th associative memory cells 107-j-1 through 107-j-n. Each of the associative memory words 102-j is concatenated to the corresponding data word line 103-j the corresponding mask word line 106-j, and comparison control line as input lines and to the corresponding mask match line 105-j and the first through the n-th shortest mask lines 114 as output lines and to the first through the n-th bit lines 113 as data input/output lines.
The k-th associative memory cells of the j-th associative memory word, 107-j-k (where k is and integer variable between 1 and n, both inclusive), is concatenated to the corresponding data word line 103-j, the corresponding mask word line 106-j, and comparison control line 104 as input lines, and to the corresponding data match line 105-j and the corresponding matched data intermediate logic line 114-k as output lines, and to the corresponding bit line 113-k as data input/output line.
The associative memory cell 107-j-k comprises a data cell 108-j-k, a comparator 110-j-k, a mask cell 109-j-k, and logical gate 111-j-k. The data cell 108-j-k is for storing “data” bit information at a corresponding bit of storage data supplied from an external source through a bit line 113-k. The comparator 110-j-k is for comparing the “data” bit information memorized in the data cell 108-j-k and the information supplied from the external source through the bit line 113-k. The mask cell 109-j-k is for storing “mask” bit information of a corresponding bit of mask information supplied from the external source through the bit line 113-k. Herein, when the bit information stored in the mask cell 109-i-k is in a valid state for mask information, an invalid state for storage data is stored in the corresponding data cell 108-j-k. 
In this embodiment, a valid state and an invalid state for the mask information are represented by “0” and “1”. A valid state and an invalid state are represented by “1” and “0”, respectively, for all of the storage data, the matched data logical-OR lines 117-1 through 117-n, and the match lines 105-1 through 105-m. 
The data cell 108-i-k stores as the storage data the state on a corresponding bit line 113-k on which the write data is driven when a corresponding data word line 103-j is in a valid state, or supplies the storage data stored therein to the corresponding bit line 113-k on which the write data is not driven when a corresponding data word line 103-j is in a valid state. When the corresponding data word line 103-j is in an invalid state, no operation is performed for the corresponding bit line 113-k. Irrespective of the state of the corresponding data word line 103-j, the storage data stored therein is supplied to the comparator 110-j-k and the logical gate 111-j-k in the same associative memory cell 107-j-k. 
The mask cell 109-j-k stores as the mask information the state on a corresponding bit line 113-k on which the write data is driven when a corresponding mask word line 106-j is in a valid state, or supplies the mask information stored therein to the corresponding bit line 113-k on which the write data is not driven when a corresponding mask word line 106-j is in a valid state. When the corresponding mask word line 106-j is in an invalid state, no operation is performed for the corresponding bit line 113-k. Irrespective of the state of the corresponding mask word line 106-j, the mask information stored therein is supplied to the comparator 110-j-k in the same associative memory cell 107-j-k. 
Prior to the start of the searching operation, the first through m-th data match line 105 is precharged to a high level to be put into a valid state “1”.
The comparator 110-j-k is supplied with the value of the search data on the corresponding bit line 113-k, the storage data stored in the data cell 108-j-k in the same associative memory cell 107-j-k, the mask information stored in the mask cell 109-j-k in the same associative memory cell 107-j-k, and the comparison control signal 104. When the comparison control signal 104 is in an invalid state “0” and the mask information is in a valid state “0”, the comparator 110-j-k puts the corresponding match line 105 into an opened state. Otherwise, if the value on the corresponding bit line 113-k and the storage data stored in the data cell 108-j-k are coincident with each other, the corresponding match line 105-j is put into an opened state. Upon incoincidence, the corresponding match line 105-j is put into an invalid state “0”. Thus, the wired AND logic concatination with the valid state “1” for the match line 105-j as true is achieved such that, when all of the comparator 110-j-1 through 110-j-n, n in number, in the associative memory word 102-j render the match line 105-j in an opened state, the match line 105 is put into a valid state “1” and otherwise into an invalid state “0”. In other words, upon the searching operation, only when the comparison control signal 104 is in an invalid state “0” and all of the storage data stored in an associative memory word 102-j is completely coincident with the bit lines 113-1 through 113-n except those bits excluded from a comparison object by the mask valid state “0” in the corresponding mask information, the match line 105-j is put into a valid state “1” and otherwise into an invalid state “0”.
The logical gate 111-j-k supplies a state “0” to the matched data intermediate line 114-k when the match line 105-j in the same associative memory word 102-j is in a valid state “1” and the storage data stored in the corresponding data cell 108-j-k in the same associative memory cell 107-j-k is in an valid state for the storage data. Otherwise, the logical gate 111-j-k puts the matched data intermediate line 114-k into an opened state. Herein, since a valid state for the storage data is represented by “1” in this embodiment, when the storage data stored in the data cell 108-j-k is in an valid state “1” and the match line 105-j is in a valid state “1”, the logical gate 111-j-k puts the corresponding matched data intermediate line 114-k into a state “0” and otherwise into an opened state.
Each of the matched data intermediate lines 114-k (where k is and integer variable between 1 and n, both inclusive) is pulled up by a corresponding register 115-k to be put into a state “1”. The matched data intermediate line 114-k is concatenated to all of the corresponding logical gates 111-1-k through 111-m-k, m in number, by a wired logic concatenation. Thus, when all of the first through m-th logical gates 111 concatenated to the corresponding matched data intermediate line 114-k render the matched data intermediate line 114-k in an opened state, the matched data intermediate line 114-k is put into a valid state “1” and otherwise into an invalid state “0”. In other words, the matched data intermediate line 114-k is concatenated by a wired AND concatenation.
Each of the logical gates 116-1 through 116-n supplies an inverted value of the corresponding matched data intermediate line 114-1 through 114-n to the corresponding matched data logical-OR line 117-1 through 117-n. 
Therefore, the matched data logical-OR line 117-k (where k is and integer variable between 1 and n, both inclusive) is supplied with the result of the logical sum operation, with the valid state for the 105 storage data as true, of all the storage data stored in the corresponding data cells 108-1-k through 108-m-k in the associative memory cells 107-1-k through 107-m-k which have the match line 105 that is in a valid state “1” upon completion of the searching operation by the logical gate 116-k, the matched data intermediate line 114-k, the resister 115-k, and corresponding logical gates 111-1-k through 111-m-k, m in number. In this embodiment, the matched data logical-OR line 117-1 through 117-n are supplied with the result of the logical sum with the valid state “1” for 105 storage data as true. As mentioned above, upon completion of the searching operation, the matched data logical-OR line 117 is supplied with the same value of the storage data coincident with the search data 112 that has the least number of bits in a invalid state “0”.
The n-bit latch 121 stores the states of the matched data logical-OR lines 117-1 through 117-n as stored states when a latch control signal 122 is in a valid state. The n-bit latch. 121 supplies the stored states to the latch output lines 120-1 through 120-n. 
With reference to the state of a selection signal 124, the two-input/one-output n-bit selector 123 selects, as output data to be supplied to the bit lines 113-1 through 113-n, either the search data 112-1 through 112-n or latch output lines 120-1 through 120-n. 
The controller 130 supplies latch control signal 122, a selection signal 124, and comparison control signal 104 synchronizing with a clock signal 131, in order to control operation of the associative memory 101.
[Detailed Description of the Conventional Associative Memory]
Next referring to FIG. 29, the associative memory cell 107 will be described. Two bit lines 113a and 113b correspond to each bit line 113 illustrated in FIG. 28. In FIG. 28, each single bit line 113-i collectively represents these bit lines 113a and 113b. Through the two bit lines 113a and 113b, writing and reading of the data into and from the memory cell and the input of the search data 112 are carried out. Upon writing the data or the input of the search data 112, the bit line 113b is supplied with an inverted value of a value on the bit line 113a. The data cell 108 is a typical SRAM (Static Random Access Memory) comprising inverted logical gates (G101 and G102) 301 and 302 with one's input and output terminals concatenated to the other's output and input terminals, respectively, a MOS (Metal Oxide Semiconductor) transistor (T101) 303 concatinateing the output terminal of the inverted logical gate (G102) 302 to the bit line 113a and rendered conductive when the data word line 103 has a high level, and a MOS transistor (T102) 304 concatinateing the output terminal of the inverted logical gate (G101) 301 to the bit line 113b and rendered conductive when the data word line 103 has the high level.
The mask cell 109 is also a typical SRAM comprising inverted logical gates (G103 and G104) 310 and 311 with one's input and output terminals concatenated to the other's output and input terminals, respectively, a MOS transistor (T108) 312 concatinateing the output terminal of the inverted logical gate (G104) 311 to the bit line 113a and rendered conductive when the mask word line 106 has the high level, and a MOS transistor (T109) 313 concatinateing the output terminal of the inverted logical gate (G103) 310 to the bit line 113b and rendered conductive when the mask word line 106 has the high level.
The comparator 110 comprises a MOS transistor (T103) 305, a MOS transistor (T104) 306, a MOS transistor (T105) 307, a MOS transistor (T106) 308, and a MOS transistor (T107) 309. The MOS transistor (T103) 305 and the MOS transistor (T104) 306 are inserted between the bit lines 113a and 113b in cascade. The MOS transistor (T103) 305 is rendered conductive when the inverted logical gate (G101) 301 in the data cell 108 produces an output of a high level. The MOS transistor (T104) 306 is rendered conductive when the inverted logical gate (G102) 302 in the data cell 108 produces an output of a high level. The MOS transistor (T106) 308 and the parallel connection of the MOS transistor (T107) 309 and the MOS transistor (T105) 307 are connected between a low potential and the match line 5 in cascade. The MOS transistor (T106) 308 is rendered conductive when the inverted logical gate (G104) 311 in the mask cell 109 produces an output of a high level. The MOS transistor (T107) 309 is rendered conductive when the comparison control signal 104 is in a valid state “1”.
The MOS transistor (T105) 307 is rendered conductive when a junction or node of the MOS transistor (T103) 305 and the MOS transistor (T104) 306 has a potential of a high level. When both the bit line 113a and the inverted logical gate (G101) 301 produce outputs of a high level or when both the bit line 113b and the inverted logical gate (G102) 302 produce outputs of a high level, the junction of the MOS transistor (T103) 305 and the MOS transistor (T104) 306 has a high level to render the MOS transistor (T105) 307 conductive.
Therefore, when the storage data stored in the data cell 108 and the search data 112 on the bit lines 113a and 113b are different from each other, the MOS transistor (T105) 307 is rendered conductive. The MOS transistor (T106) 308 is put into an opened state and conductive state when the mask information stored in the mask cell 109 is “0” and “1”, respectively. The word match line 105 is precharged to a high potential prior to the start of the searching operation. This provides the wired AND concatenation such that, when a plurality of the associative memory cells 107 are concatenated to the match line 105 through both the MOS transistors (T106) 308 and the MOS transistors (T107) 309, the match line 105 is given a low level if at least one associative memory cell 107 produces an output of a low level.
When MOS transistor (T105) 307 is conductive and either of the MOS transistor (T106) 308 or the MOS transistor (T107) 309 is conductive, the associative memory cell 107 supplied an invalid state “0” to the match line 105. Otherwise, the match line 105 is put into an opened state. Specifically, when the mask information is in a valid state “0” and the comparison control signal 104 is in an invalid state “0”, the match line 105 is put into an opened state irrespective of the comparison result between the search data 112 and the storage data. Otherwise, the match line 105 is put into an opened state and supplied with an invalid state “0”, when the search data 112 on the bit lines 113a and 113b and the storage data stored in the data cell 108 are coincident with each other and different from each other, respectively.
Next, the logical gate 111 and the matched data intermediate line 114 will be described. The matched data intermediate line 114 is pulled up by a resister 115 (FIG. 28) to be put into a state “1” prior to a searching operation. The logical gate 111 comprises MOS transistors (T110 and T111) 314 and 315 concatenated in cascade between the matched data intermediate line 14 and a low potential. The MOS transistor (T110) 314 is put into a conductive state and an opened state when a match line 105 is in a valid state “1” and an invalid state “0”, respectively. The MOS transistor (T111) 315 is put into a conductive state and an opened state when an inverted logical gate (G102) 302 in the data cell 108 produces an output of a high level and a low level, respectively, i.e., when the storage data stored in the data cell 108 is in an valid state “1” and a invalid state “0”, respectively. Thus, the logical gate 111 supplies an state “0” to the matched data intermediate line 114 when the match line 105 is in a valid state “1” and the storage data stored in the data cell 108 is in an valid state “1”. Otherwise, the logical gate 111 puts the matched data intermediate line 114 into an opened state.
[Operation of the Conventional Associative Memory]
Next referring to FIG. 30, description will be made about the operation when the above-mentioned associative memory 101 is used in calculating the transfer network address in the network device 400-1 in FIG. 33. Referring to FIG. 31, this operation will be described by the use of a timing chart.
It is assumed here that the associative memory 101 comprises three words of nine bits. The associative memory 101 memorizes the concatenation information in the associative memory words 102-1 through 102-3 except the network address (1, *, *) of the network device 400-1 in FIG. 33. Herein, when a digit of a network address is represented by the symbol “*” as “don't care”, the corresponding bit of the storage data is stored with an invalid state “0” for the storage data, and the corresponding bit of the mask information is stored with a valid state “0” for the mask information.
Specifically, the associative memory word 102-1 stores in binary numbers the storage data (010, 000, 000) and the mask information (111, 000, 000) to implement (2, *, *). Likewise, the associative memory word 102-2 stores in binary numbers the storage data (010, 011, 000) and the mask information (111, 111, 000) to implement (2, 3, *). The associative memory word 102-3 stores in binary numbers the storage data (011, 000, 000) and the mask information (011, 000, 000) to implement (3, *, *).
Description will proceed to the searching operation by supplying as the search data 112 the network address (2, 3, 4), in octal numbers, of the user's terminal (PC) 401-2 in FIG. 112. At first, all of the match lines 105-1 through 105-3 are precharged to a high level (“1”) to be put into a valid state “1” at the timing (1) in FIG. 31.
Next, the two-input/one-output 8-bit selector 123 is responsive to the selection signal 124 which the controller 130 supplies, and selects the search data 112 to deliver the search data 112 to the bit lines 113-1 through 113-9 at the timing (2) in FIG. 31. The controller 130 puts the comparison control line 104 into an invalid state “0” in order to permit each of the associative memory cells 107-1-1 through 107-m-n to puts the corresponding match line 105 into an opened state irrespective of the comparison result between the search data 112 and the storage data stored therein when the mask information stored therein is in a valid state “0”. In other words, the searching operation is carried out taking the “don't care” state represented by the symbol “*” into account. Therefore, the octal notations (2, *, *), and (2, 3, *) respectively stored in the associative memory words 102-1, and 102-2 in the associative memory 101 are coincident with the search data 112 on the bit lines 113-1 through 113-9. Accordingly, as a result of the primary searching operation, the match lines 105-1, and 105-2 are put into a valid state “1” while the remaining match line, 105-3, is put into an invalid state “0”.
Herein, the matched data logical-OR line 117-1 produces the logical sum “0”, with “1” as true, of the storage bit data “0”, in the memory words 102-2 at bit positions corresponding to the matched data logical-OR line 117-1. The matched data logical-OR line 117-2 produces the logical sum “1”, with “1” as true, of the storage bit data “1”, in the memory words 102-1 at bit positions corresponding to the matched data logical-OR line 117-2. Likewise, the matched data logical-OR lines 117-3, 117-4, 117-5, 117-6, 117-7, 117-8, and 117-9 produce the logical sum “0” of “0” and “0”, the logical sum “0” of “0” and “0”, the logical sum “1” of “0” and “1”, the logical sum “1” of “0” and “1”, the logical sum “0” of “0” and “0”, the logical sum “0” of “0” and “0”, and the logical sum “1” of “0” and “0”, respectively, “1” as true. As a result, the binary notation “010011000” is delivered to the matched data logical-OR lines 117-1 through 117-9.
In this state, the controller 130 puts the latch control signal 122 into valid state. The n-bit latch 121 stores the states of the matched data logical-OR lines 117-1 through 117-9. Accordingly, the n-bit latch 21 stores the binary notation “010011000”. The n-bit latch 121 delivers the stored state “010011000” to the latch output line 120-1 through 120-9.
The timing (3) in FIG. 31 is inserted in order to arrange the state of the clock signal 131 of the timing (2) and the timing (4) so that the associative memory 101 holds the states of the timing (2).
At the timing (4) in FIG. 31, in response to the selection signal 124 which the controller 130 supplies, the two-input/one-output n-bit selector 123 selects the latch output line 120 and supplies the information “010011000” on the latch output line 120 to the corresponding bit lines 113-1 through 113-9. Thereafter, the associative memory 101 starts a secondary searching operation. In the secondary searching operation, use is made of the states of result of the primary searching operation at the timing (2) that is maintained on the match lines 105-1 through 105-3. In this example of the operation, the two match lines 105-1 and 105-2 maintain a valid state “1” while the match line 105-3 maintains an invalid state “0”. The controller 130 puts the comparison control signal 104 into valid state “1”. Thus, each of the associative memory cells 107-1-1 through 107-m-n to puts the corresponding match line 105 into an invalid state “0” irrespective of the mask information stored therein when the storage data stored therein is different from the states of the bit lines 113-1 through 113-9. In other words, the secondary searching operation is carried out irrespective of the “don't care” state represented by the symbol “*”. Therefore, the match line 105-1 through 105-3 is put into an invalid state “0” when the storage data stored in the corresponding associative memory word 102-1 through 102-3 is different from the states “010011000” of the bit lines 113-1 through 113-9.
In this example of the operation, the storage data stored in the associative memory word 102-2 is completely coincident with the states “010011000” on the bit lines 113-1 through 113-9 so that the corresponding match line 105-2 is put into an opened state. Since the storage data stored in any other associative memory words 102-1 and 102-3 is not coincident, the corresponding match lines 105-1 and 105-3 are supplied with an invalid state “0”. Thus, in the match line 105-1, and 105-2 that maintain a valid state “1” prior to the start of the secondary searching operation, the only match line 105-2 can maintain a valid state “1” upon completion of the secondary searching operation.
It will therefore be understood that, in the match lines 105 corresponding to one of the storage data coincident with the search data 112 taking the mask information into account, the only match line 105-2 corresponding to the storage data with the least number of bits in a mask valid state is put into a valid state.
The conventional associative memory 101 can not produce the storage data with the least number of bits in a mask valid state in the mask information field corresponding to one of the storage data field, which also corresponds to each network address, coincident with the plurality of the network address supplied for searching operation taking the mask information into account, when the plurality of the network address pair of the storage data and the mask information is memorized in one associative memory word, as follows.
Next referring to FIG. 32, description will be made about one example of the operation when the conventional associative memory 101 is used in determination of the transfer permission for the data transfer from PC401-1 with network address (1, 2, 6) to PC401-3 with network address (2, 3, 5).
The transfer rule 1 through 5 in the Table 1(b) defines that the pair of the structured data composed of the storage data and mask information is memorized in which each pair of structured data comprises 18 bits of concatenated storage data, with 9 bits of source network address and 9 bits of destination network address, and 18 bits of mask information with each 9 bits of corresponding mask information.
It is assumed here that the associative memory 101 comprises five words of eighteen bits. The nine bits of structured data of the source network address under each transfer rule in Table 1(b) combines nine bits of storage data and nine bits of mask information. Herein, each nine bits of storage data and nine bits of mask information is stored as the upper nine bits of each storage data and mask information of associative memory word 102-1 through 102-5 corresponding to each transfer rule. Likewise, the nine bits of structured data of the destination network address under each transfer rule in Table 1(b) combines nine bits of storage data and nine bits of mask information. Herein, each nine bits of storage data and nine bits of mask information is stored as the lower nine bits of each storage data and mask information of the associative memory word 102-1 through 102-5 corresponding to each transfer rule. As a result, eighteen bits of the structured data stored in the associative memory word 102-1 through 102-5 will be described as FIG. 32 shows.
Like the operation described above, in the primary searching operation, the search data 112 (1, 2, 6 2, 3, 5), in octal numbers, is supplied to the bit line 113, and associative memory 101 compares it regarding the storage data 10 associative memory word 102-1 through 102-5 and corresponding mask information. Therefore, the octal notations (1, 2, * 2, *, *), (1, 2, * 2, 3, *), (1, *, * 2, 3, 5) respectively stored in the associative memory words 102-1, 102-3 and 102-5 in the associative memory 101 are coincident with the search data 112 on the bit lines 113. Accordingly, as a result of the primary searching operation, three data match lines 105-1, 105-3 and 105-5 are put into a valid state “1” while the remaining data match lines 105-2, and 105-4 are put into an invalid state “0”.
Herein, like the operation described above, in associative memory word 102-1 through 102-5, the result of the logical-OR of the eighteen bits of storage data, which corresponding match line 105 holds valid state “1”, is stored in the n-bit latch 102 with the valid state “1”, as true. Accordingly, the n-bit latch 121 stores the logically OR with the data stored in the associative memory word 102-1, 102-3, and 102-5, which is represented by (1, 2, 0, 2, 0, 0), (1, 2, 0, 2, 3, 0), and (1, 1, 0, 2, 3, 5) in octal notation respectively, and “001, 010, 000, 010, 000, 000”, “001, 010, 000, 010, 011, 000” and “001, 000, 000, 010, 011, 101” in binary notation respectively. The result of logical-OR is represented by (1, 2, 0, 2, 3, 5), in octal notation and “001, 010, 000, 010, 011, 101”, in binary notation. Then the n-bit latch 121 stores this result and delivers it to the latch output line 120.
Like the operation described above, in the secondly searching operation, supply the search data 112 represented by (1, 2, 6 2, 3, 5), “001, 010, 000, 010, 011, 101”, in octal notation and binary notation respectively, is supplied to the bit line 113, and compares it with the storage data stored in the associative memory word 102-1 through 102-5 and without regard to corresponding mask information. Accordingly, all the storage data stored in the associative memory word 102-1 through 102-5 are not coincident with each other, while all the match lines 105-1 through 105-5 are put into an invalid state “0”.
It is assumed here that the data transfer from PC401-1 with network address (1, 2, 6) to PC401-3 with network address (2, 3, 5) will be prohibited by the transfer rule 3. In other words, the only match line 105-3 corresponding to the associative memory word 102-3 is supposed to be put into valid state “1”. However, as described above, the match line 105-1 through 105-5 in the conventional associative memory are in an invalid state after searching operation.
Therefore, in order to ensure the security of the network, a function of determination of transfer permission based on the transfer rule to the source network address and destination network address of input transfer data is implemented by CPU using software processing with binary-tree-search algorithm in the conventional network devises as described above. This software processing requires hundreds of clock or more. Besides, even fast calculation of transfer network address is provided by an associative memory, the whole data transfer rate of the whole network declines if the security of the network is ensured.
In case of the determination of transfer permission by software processing with binary-tree-search algorithm, huge search table is required in advance. Therefore, transfer operation of network device is suspended while transfer rule is deleted, added, or changed. Consequently, since deletion, addition, or change of transfer rule is not operated frequently by a network administrator, whole network is operated under low security.
Furthermore, high speed determination of transfer permission requires costly high-speed CPU system, which means total cost of network device increase overall.
It is therefore an object of this invention is to provide an associative memory which produces the signal identifying particular word with the least number of bits in a valid state of mask information comparing, with order of priority, the number of bits in a valid state of mask information which consists of structure data at each field when two or more words are found, all of which storage data coincident with corresponding input data, in the searching operation against input data composed of plural search field taking mask information into account.
It is another object of this invention to provide a network devise which is capable of carrying one fast determination of transfer permission to input data based on transfer rule.
It is still another object of this invention to provide a network devise with ability of frequent deletion, addition, or change of transfer rule without suspending the transfer operation.
It is still another object of this invention to reduce the total cost of network devise with fast determination of transfer permission.
It is still another object of this invention to provide network system which is capable of ensuring the security with high data transfer rate.